package main

import "fmt"

//能用但是不符合时间要求
func search(nums []int, target int) int {
	mid := len(nums) / 2
	l, r := 0, len(nums)-1
	if target == nums[mid] {
		return mid
	} else if r == 0 {
		return -1
	}
	//右边数组长
	if nums[0] > nums[mid] {
		//在中位数右边那一段
		if target > nums[mid] && target < nums[0] {
			l = mid + 1
		} else if target > nums[mid] { //在左边较高那一段
			if nums[r] < nums[0] {
				r--
			}
			//在中间较低那一段
		} else if target < nums[mid] {
			for target < nums[mid] {
				r = mid - 1
				mid = (r + l) / 2
			}
			if target == nums[mid] {
				return mid
			}
			for ; mid < r; r-- {
				if target == nums[r] {
					return r
				}
			}
			return -1

		}
		//左边数组长
	} else if nums[0] < nums[mid] {
		//在左边数组较低处
		if target < nums[mid] && nums[0] < target {
			//在右边数组
		} else if target < nums[mid] && nums[0] > target && nums[0] > nums[r] {
			l = mid + 1
			for nums[l] > nums[0] {
				l++
			}
			//在左边数组较高处
		} else if target > nums[mid] {
			l = mid
			for nums[r] < nums[0] { //如果没有右边数组，则不满足条件跳过此环节
				r--
			}
		}
	}
	for l <= r {
		mid = (l + r) / 2
		if target == nums[mid] {
			return mid
		} else if target < nums[mid] {
			r = mid - 1
		} else {
			l = mid + 1
		}
	}
	return -1
}

//借鉴其他解法
func search1(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := (right + left) / 2
		if nums[mid] == target {
			return mid
		}
		if nums[mid] >= nums[left] {
			if nums[mid] > target && target >= nums[left] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			if nums[mid] < target && target <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}
	return -1
}

func main() {
	s1 := []int{3, 1}
	fmt.Println(search(s1, 7))
	fmt.Println(search1(s1, 7))
}
